/*
  链表：ES6对象封装链表
*/
function defaultEquals(a, b) {
  return a === b;
}
// 节点类
class Node {
  constructor(element) {
    this.element = element;
    this.next = undefined;
  }
}

// 单链表类
class LinkedList {
  constructor(equalsFn = defaultEquals) {
    this.count = 0;
    this.head = undefined;
    this.equalsFn = defaultEquals;
  }
  // 链表尾部插入
  push(element) {
    const node = new Node(element); // 创建一个新节点
    let current; // 用于遍历得到尾部节点
    if (this.head == null) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next != null) {
        // 遍历得到尾节点
        current = current.next;
      }
      current.next = node;
    }
    this.count++;
  }

  // 删除特定位置元素
  removeAt(index) {
    // 检查越界值
    if (index >= 0 && index < this.count) {
      let current = this.head;

      // 移除第一项
      if (index == 0) {
        this.head = current.next;
      } else {
        let previous;
        for (let i = 0; i < index; i++) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }

  // 删除特定值元素
  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }

  // 特定位置插入元素
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      if (index === 0) {
        // 第一个位置插入
        node.next = this.head;
        this.head = node;
      } else {
        const previous = this.getElementAt(index - 1); // 上一个节点
        const current = previous.next;
        node.next = current;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

  // 返回特定位置节点
  getElementAt(index) {
    // 合法性判断
    if (index >= 0 && index <= this.count) {
      let current = this.head;
      for (let i = 0; i < index && current != null; i++) {
        current = current.next;
      }
      return current;
    }
    return undefined;
  }

  // 返回元素索引
  indexOf(element) {
    let current = this.head;
    for (let i = 0; current != null && i < this.count; i++) {
      if (this.equalsFn(element, current.element)) {
        return i;
      }
      current = current.next;
    }
    return -1;
  }

  // 是否为空
  isEmpty() {
    return this.size() === 0;
  }

  // size()
  size() {
    return this.count;
  }

  // 获取头部节点
  getHead() {
    return this.head;
  }

  // toString()
  toString() {
    if (this.head == null) return "";
    let res = "";
    let current = this.head;
    for (let i = 0; i < this.size() && current != null; i++) {
      res += current.element;
      current = current.next;
    }
    return res;
  }
  // reverseBetween  (left, right) {
  //   if (left > 0 && right > 0 && left <= right) {
  //     // 参数合法性
  //     if (left === right) {
  //       // 不用处理
  //       return this.head;
  //     } else {
  //       let previous_left; // 反转起始节点的前一个节点
  //       let current_right = this.head; // 反转终止节点
  //       let stack = [];
  //       let i = 1;
  //       while (true) {
  //         if (i > left - 1) {
  //           previous_left = current_right;
  //         }
  //         if (i >= left) {
  //           stack.push(current_right);
  //         }
  //         if (i >= right) break;
  //         current_right = current_right.next;
  //         i++;
  //       }

  //       //尾部
  //       previous_left.next.next = current_right.next;

  //       // 内部反转
  //       let current = previous_left;
  //       while (stack.length !== 0) {
  //         current.next = stack.pop();
  //         current = current.next;
  //       }
  //       return this.head;
  //     }
  //   }
  //   return null;
  // };
}

// let linkedlist = new LinkedList();
// for (let index = 1; index < 10; index++) {
//   linkedlist.push(index);
// }

console.log(linkedlist.reverseBetween(2, 9));

module.exports = {
  Node,
  defaultEquals,
  LinkedList,
};
